#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年07月13日
描    述：
'''


class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """

        size = len(edges)
        res = list()
        if n == 1:
            return [0]

        ads = [list() for _ in range(n)]

        for i in range(size):
            j, k = edges[i][0], edges[i][1]
            ads[j].append(k)
            ads[k].append(j)

        newleave = []
        for i in range(n):
            if len(ads[i]) == 1:
                newleave.append(i)

        leave = newleave
        while n > 2:
            n -= len(leave)
            newleave = []
            for i in leave:
                j = ads[i][0]
                ads[j].remove(i)

                if len(ads[j]) == 1:
                    newleave.append(j)
            leave = newleave

        for i in leave:
            res.append(i)

        return res
